package com.zk.algorithm.greedy;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/boats-to-save-people/
 *
 * @author zk
 */
public class BoatsToSavePeople {

    //
    // people = [3,5,3,4], limit = 5
    public int numRescueBoats(int[] people, int limit) {
        // 3,3,4,5
        Arrays.sort(people);
        //
        int i = 0;
        int j = people.length - 1;

        int ans = 0;

        // 尺取法
        // 3, 3, 4, 5
        // ↑        ↑
        // ↑     ↑
        // ↑  ↑
        // ↑
        //
        // 尺取法
        // 1, 2, 2, 3
        // ↑        ↑
        // ↑     ↑
        //    ↑  ↑
        //    ↑
        while (i <= j) {
            ans++;

            // 最重的 + 最轻的
            // 每艘船最多载重两个人
            if (people[i] + people[j] <= limit) {
                i++;
            }

            j--;
        }

        return ans;
    }

}